package com.xaicode.algorithm.leetcode._101_200;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode-cn.com/problems/majority-element">多数元素</a>
 *
 * <p>给定一个大小为 <em>n </em>的数组，找到其中的多数元素。多数元素是指在数组中出现次数 <strong>大于</strong> <code>⌊ n/2 ⌋</code> 的元素。</p>
 *
 * <p>你可以假设数组是非空的，并且给定的数组总是存在多数元素。</p>
 *
 * <p> </p>
 *
 * <p><strong>示例 1：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>[3,2,3]
 * <strong>输出：</strong>3</pre>
 *
 * <p><strong>示例 2：</strong></p>
 *
 * <pre>
 * <strong>输入：</strong>[2,2,1,1,1,2,2]
 * <strong>输出：</strong>2
 * </pre>
 *
 * <p> </p>
 *
 * <p><strong>进阶：</strong></p>
 *
 * <ul>
 * 	<li>尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。</li>
 * </ul>
 *
 * @author Locker xaicode@sina.com
 * @version 1.0
 * @date 2021/12/6 0006 20:50
 */
public class _169_Easy_MajorityElement {

    /**
     * count(1): 3
     * count(2): 4
     */
    public int[] nums = new int[]{2, 2, 1, 1, 1, 2, 2};

    public static void main(String[] args) {
        final _169_Easy_MajorityElement majorityElement = new _169_Easy_MajorityElement();

        final int sort = majorityElement.sort();

        System.out.println(sort);
    }

    /**
     * 方法一：
     * 如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，
     * 那么下标为 2/n 的元素（下标从 0 开始）一定是众数
     * <p>
     * 时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)。
     * <p>
     * 空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。
     * 如果自己编写堆排序，则只需要使用 O(1) 的额外空间
     *
     * @return majorityElement
     */
    public int sort() {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 方法二：哈希表
     * <p>
     * 使用哈希映射（HashMap）来存储每个元素以及出现的次数。
     * 对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数
     * <p>
     * 用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。
     * 在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。
     * 我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     *
     * @return majorityElement
     */
    public int hash() {
        Map<Integer, Integer> counts = countNums(nums);
        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }
        return majorityEntry.getKey();
    }

    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                counts.put(num, counts.get(num) + 1);
            }
        }
        return counts;
    }

}
